package 二分查找;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 搜索旋转数组.java
 * @Description TODO
 * @createTime 2020年11月06日 08:58:00
 * 给你一个升序排列的整数数组 nums ，和一个整数 target 。
 *
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
 *
 * 请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 *
 *  
 * 示例 1：
 *
 * 输入：nums = [4,5,6,7,0,1,2], target = 0
 * 输出：4
 *
 */
public class 搜索旋转数组 {
    public class Solution {

        public int search(int[] nums, int target) {
            int len = nums.length;
            if (len == 0) {
                return -1;
            }

            int left = 0;
            int right = len - 1;
            while (left < right) {
                int mid = left + (right - left  + 1) / 2;
                //用中间值和右端点进行比较
                if (nums[mid] < nums[right]) {

                    if (nums[mid] <= target && target <= nums[right]) {
                        left = mid;
                    } else {
                        right = mid - 1;
                    }

                } else {



                    if (nums[left] <= target && target <= nums[mid - 1]) {
                      right = mid - 1;
                    } else {
                      left = mid;
                    }
                }
            }

            if (nums[left] == target) {
                return left;
            }
            return -1;
        }
    }
}

